Recursion Practice

Table of Contents

This assignment is to be done individually. You can talk to other people in the class, me (Dave), the prefect, and lab assistants for ideas and to gain assistance. You can help each other debug programs, if you wish. The code that you write should be your own, however, and you shouldn’t hand a printout of your program to others. See the course syllabus for more details or just ask me if I can clarify.

1. Overview

It’s time to get some practice writing recursion!

For all of these exercises, you must do them recursively.

It is very challenging to pose small introductory recursion problems for which online examples aren’t readily available. Answers to all of these problems are online in some form. My goal is not to pose assignments which are scavenger hunts: I know that you can use Google. The goal of this assignment is to learn by doing, and via the struggle. If you just look up the solution, it won’t help you get better at writing recursive code yourself, and it won’t help you be able to answer the recursion questions that will be on the last in-class exam.

I won’t forbid the use of looking it up online, but I would discourage you from doing so. If you do, you should not copy it. Instead, read it, understand it (ask for help if you don’t know how), and then do something else for at least 15 minutes. Then see if you can code it yourself.

2. Get started

Create a folder in which to store your work for this assignment.

  • If you are working on your own computer, it’s up to you where to put the folder. Your desktop is likely as good a place as any. Make a folder titled recursion.
  • If you are working in the labs in Olin, make sure to first mount the COURSES folder, so that you won’t lose your code when you log out. Once you’ve done so, open up Finder, then navigate to your personal student work folder. You can then make a recursion folder within there.
  • Once you’ve done so, you should then open up your new folder in VS Code. To do so, start up VS Code, then drag your folder onto the VS Code window. This should open up the folder within VS Code. If you are asked, click that you trust the authors.

3. Functions you will write

3.1. Maximum

listmax(numberlist) should take a list of parameters as a parameter, and return the largest. Hint: the largest in the entire list is the larger of the first item and the listmax of all the other items. You may not use the built in functions max, min, or any other function that would similarly make this trivial.

3.2. Palindrome

palindrome(word) should return True or False, depending on whether or not the word is a palindrome. A palindrome is a word that reads the same forward or backwards, such as “racecar”. You may assume that the word contains only letters, all in lower case, with no spaces or punctuation. You should NOT do this assignment by reversing the string and testing if the reversed string and the original are the same. Hint: check if the first and last letters are the same, then see if what is left is a palindrome.

4. Exemplary

4.1. Elements Less Than

If you complete the above functionality, you should feel proud and good about yourself that you have gotten this far, and feel free to stop here! If you want to try to go for the E grade, write the function below.

getElementsLessThanValue(value,lst) should take a value, and a list. The function should then return a list containing all values in the original list that are less than value, in the same order that they appeared in the original list. For example, getElementsLessThanValue(5, [2,9,3,1,4,5,7]) should return [2, 3, 1, 4].

5. Grading

You will receive an M for this assignment if…

  • Your code passes all tests when we run pytest tests_m.py. Here is the tests_m.py file.
  • Your program is written to work in general, and not to only work for the specific tests that we have provided.
  • Your code must contain no loops at all. (No for or while loops allowed.) I’m sometimes asked by students for this assignment if that means you are prohibited from using “an if loop”; this is a fine time to point out that if isn’t a loop!

  • Your code must be recursive, and the recursive code must be relevant for actually solving the problem at hand. The following sample code is an example of a program that technically does recursion, but the recursion is entirely irrelevant: 

    def printWithUselessRecursion(s):
    if len(s) == 1:
        return s
    printWithUselessRecursion(s[0])
    print(s)

You will receive a grade of E for this assignment if you satisfy the above M requirements, and …

  • your programs have a comment at the top of each function with at least 5 words describing what the function does.
  • every one of your variable names is meaningful in some way. (Names such as thing, number, etc. are not meaningful.)
  • You have at least one other comment near what you think is the trickiest part of your code, describing how it works
  • your code demonstrates a clear sequence of actions to achieve the goal at hand, and each piece is essential. Your code does not have notably more cases or conditions than it needs to.
  • Your code passes all tests when we run pytest tests_e.py. Here is the tests_e.py file.

6. Submit your work

When finished, zip up your code and submit your work through Moodle.

Good luck, and have fun! Remember that lab assistants are available to help out if you need it, and you can attend prefect sessions as well.

Author: Dave Musicant